package algorithm.search;

import algorithm.tree.BinaryNode;

/**
 * 二叉排序树
 */
public class BinarySortTree<E> {
    protected BinaryNode<E> root; //根结点

    public BinarySortTree() {
        root = null;
    }
    public boolean isEmpty(){
        return false;
    }
    //中根次序遍历二叉排序树
    public void inOrder() {

    }
    //中根次序遍历子树
    public void inOrder(BinaryNode<E> p ) {}

    //根据值查找结点
    public BinaryNode search(E value) {
        if(value==null || !(value instanceof Comparable))
            return null;
        Comparable compobj = (Comparable) value;
        BinaryNode p = this.root;
        while(p!=null && compobj.compareTo(p.data)!=0) {//没有相等的
            System.out.println(p.data+"?");
            if(compobj.compareTo(p.data) < 0 ) {//进入左子树
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return p;
    }
    //插入结点，不插入关键字重复的结点，成功返回true
    public boolean insert(E value) {
        if(value==null || !(value instanceof Comparable))
            return false;
        if(root == null) {
            root = new BinaryNode<E>(value);
            return true;
        }
        return insert(value,root);
    }
    public boolean insert(E value,BinaryNode<E> p) {
        Comparable compobj = (Comparable) value;
        if(compobj.compareTo(p.data) == 0){
            return false;
        }
        if(compobj.compareTo(p.data) < 0) { //左操作
            if (p.left ==null){
                p.left=new BinaryNode<E>(value);
                return true;
            }
            else{
                return insert(value,p.left);
            }
        }
        else {
            if(p.right==null){ //右操作
                p.right = new BinaryNode<E>(value);
                return true;
            }
            else{
                return insert(value,p.right);
            }
        }
    }
    //删除结点，若删除成功返回删除结点值，否则null
    public E remove(E value){
        if(root==null || value==null||!(value instanceof Comparable))
            return null;
        return remove(value,root,null);
    }
    //在以p为根的子树中删除value，parent是p的父母结点，递归算法
    public E remove(E value,BinaryNode<E> p,BinaryNode<E> parent){
        Comparable comobj = (Comparable)value;
        if(p!=null){
            if(comobj.compareTo(p.data)<0)
                return remove(value,p.left,p);
            else{
                if(comobj.compareTo(p.data)>0)
                    return remove(value,p.right,p);
                else{
                    if(p.left!=null && p.right!=null){ //p为2度结点
                        BinaryNode<E> innext = p.right; //寻找P在中根次序下的后继结点
                        while (innext.left!=null){
                            innext = innext.left;
                        }
                        p.data = innext.data; //以后继结点值替换
                        return remove(p.data,p.right,p);
                    }
                    else { //p是1度和叶子结点
                        if(parent==null){ //删除根结点，即p=root
                            if(p.left!=null)
                                root = p.left;
                            else
                                root = p.right;
                            return p.data;
                        }
                        if(p == parent.left){ //p是parent的左孩子
                            if(p.left!=null)
                                parent.left = p.left; //p的左子树填补
                            else
                                parent.left = p.right;
                        }
                        else{ //p是parent的右孩子
                            if(p.left!=null)
                                parent.right = p.left;
                            else
                                parent.right = p.right;

                        }
                        return p.data;
                    }
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        BinarySortTree bstree = new BinarySortTree<Integer>();
        System.out.println("插入：");
        int[] key = {54,18,66,87,36,12,54,81,15,76,57,6,40,99,85};
        for (int i=0;i<key.length;i++){
            if(bstree.insert(new Integer(key[i])))
                System.out.println(key[i]+" ");
        }
        bstree.inOrder();
        Integer element = new Integer(key[key.length-1]);
        System.out.println("查找"+element+","+(bstree.search(element)!=null?"":"不")+"成功");
        element = new Integer(50);
        System.out.println("查找"+element+","+(bstree.search(element)!=null?"":"不")+"成功");
        System.out.println("用时:"+(System.currentTimeMillis()-startTime)+"ms");
        /*
        运行结果：
        查找85,成功
        查找50,不成功
        用时:2ms
         */
    }
}
